Non-patent document 1 shows a conventional quantum bit string commitment (Quantum Bit String Commitment, QBSC). QBSC is a variation of bit commitment (Bit Commitment, BC; see Non-patent document 2, for example).
BC is a kind of cryptography protocols. An object of BC is to send an evidence of a bit bε{0,1} determined by a sender (Alice, hereinafter) at a certain time to a receiver (Bob, hereinafter) without sending the value b itself.
As an application of BC, for example, it is assumed that Alice and Bob play Japanese chess using a communication channel without actually facing each other. When one day's game is finished, in order to commit a sealed move, Alice records the result as b=0 or b=1. Or, if it is complex, the move is encoded into a bit string B=(b1, . . . , bn), and each bi is recorded.
At this time, Alice does not want to open the value of b to Bob until the next day and on the other hand, Bob wants Alice not to change the value of b later. However, since they play over the communication channel, it is impossible to write on paper and pack the paper in an envelope or a safe.
Accordingly, it is decided that Alice sends Bob a certain data string Db that can be an evidence. When the time comes to release the sealed move, b is opened to Bob. Bob compares b with Db, and accepts that the sealed move is correct if there is no contradiction.
BC can be used as the sealed move, because BC is under condition that it is hard for Bob to obtain the value b from the value Db, and furthermore it is hard for Alice to change b after sending Db (requirement of security of BC will be discussed later). Namely, BC plays a role of a safe or an envelope.
The above example is merely one of application forms. The importance of BC is that it is a basic component of various cryptography protocols (see Non-patent document 2). BC is also used for a protocol of well-known electronic voting.
Hereinafter, a series of operations in which Alice sends Bob an evidence of b is referred to as “commit phase (Commit Phase),” and to perform the operations is referred to as “to commit.”
Further, a series of operations in which when a certain time period has passed after the commit phase, Alice opens b, and Bob compares b with the evidence to confirm that b is correct is referred to as “open phase (Open Phase).”
In the open phase, that Bob concludes “b is correct” is called “to accept (Accept) the commitment,” and that Bob concludes “b is not correct, or the evidence is not enough to prove b is correct” is called “to reject (Reject) the commitment.”
The commit phase of BC is defined as follows (refer to Non-patent document 2):
(A1) Alice determines a value of bit bε{0, 1}.
(A2) Alice computes electronic data Db corresponding to b and sends (commits) to Bob.
(A3) Bob records the electronic data Db in a recording device to maintain.
Further, the open phase of BC is defined as follows (refer to Non-patent document 2):
(A4) Alice sends a value of bit b and associated information D′ to Bob.
(A5) Bob computes using b, D′, and Db and checks if there is contradiction among these values. If no contradiction, “Accept” is output (commitment is accepted). If there is contradiction, “Reject” is output (commitment is rejected).
Although various methods are known as a method to compose D′ and Db corresponding to the bit b, here, it is noted a method using cryptologic hash function, for example. In this case, for computing Db, Alice selects a random number rε{0, 1}R−1, and first obtains D=r∥b by connecting b to r. Then, Db=H(D) is computed using the cryptologic hash function H (SHA-1, for example).
At this time, grounds for security of BC is that it is difficult, when an output F of the cryptologic hash function is given, to obtain a corresponding input I (namely, I that satisfies F=H(I)). That is, difficulty of computing amount is the grounds for the security of BC.
Requirements for the security of BC is as follows (refer to Non-patent document 2):
(Concealing) It is difficult for Bob to know the value of b prior to the open phase.
(Binding) It is difficult for Alice to change the value of b after the commit phase.
Although BC is important as components of cryptography protocol, it is necessary to assume calculation amount difficulty in order to prove its security at present (see Non-patent document 2). However, due to the introduction of new algorithm and a quantum computer, etc., the calculation amount difficulty may be resolved (for example, in public key cryptography, difficulties of prime factorization problems and discrete logarithm problems are basis for security (see Non-patent Document 2, for example). However, if the quantum computer comes into practical use, these problems can be solved effectively, so that it is known that the public key cryptography loses its security (see Non-patent document 3).), so that it is impossible to guarantee absolute security.
On the other hand, in case of configuring cryptographic protocol based on quantum theory, the security can be absolute (see Non-patent document 3, for example). In fact, quantum key distribution (QKD, see Non-patent document 4) is known as an example of such. However, it is disclosed that it is impossible to guarantee the security of BC by using only quantum theory (Non-patent document 5). Then, by loosing the requirement for the security a little, QBSC is provided by implementing cryptography protocol (by quantum theory) similar to BC.
Hereinafter, quantum bit string commitment (QBSC) will be explained.
QBSC is a method to commit not a single bit but a bit string B=(b1, . . . , bm) at once (Non-patent document 1). It should be noted that this is different from individual operation of BC for each bit bi. This is because the requirement for the security, in particular Concealing requirement has been changed. In QBSC, a certain limited number of bits can be leaked among information of the bit string B.
FIG. 7 shows a conceptual diagram showing a conventional quantum bit string commitment method shown in Non-patent document 1.
The commit phase of the method according to Non-patent document 1 is defined as follows:
(B1) Alice selects a bit string B=(b1, . . . , bm) that she wants to commit.
(B2) Alice sends Bob state |ΨB corresponding to B through quantum channel.
(B3) Bob maintains the received |ΨB.
In the above procedure, the state |ΨB that Alice sends Bob is “an evidence of the bit string B.” However, even if there is |ΨB, information amount from which Alice can know about the bit string B is limited. The theoretical basis for this is given by Holevo's bound (see Non-patent document 6, for example).
“To send the state |ΨB” means to send a quantum having the state |ΨB. For example, in case of using light, it is assumed to consider polarization state as the state |ΨB. At this time, “to send the state |ΨB” means “to send light in a certain polarization state.”
Since everything in the world consists of quantum, anything can be sent. However, whether the quantum state can be stably maintained is a different question, which depends on each quantum to be handled. For example, light is superior, because light can keep mutual interaction with environment small within fiber optic or free space, and it is often used in quantum key distribution (see Non-patent documents 2, 3 and 4). Polarization of a single photon is used as the earliest implementation method of the quantum key distribution (see Non-patent document 7 or 8). Further, in the quantum key distribution, another method, in which a phase difference between wave packets is used instead of the polarization state, is known (see Non-patent document 9).
Next, the open phase of Non-patent document 1 is defined as follows:
(B4) Alice sends Bob the bit string B through a classical channel.
(B5) Bob observes the maintained state |ΨB, and confirms if there is no contradiction between the observed result and the contents of the bit string B.
(B6) If there is any contradiction during the observation at step 2, Bob rejects Alice's commitment. If there is no contradiction, Bob accepts Alice's commitment.
Although requirements for the security in QBSC are similar to ones in case of BC, they are changed as follows:
Where blk, r, and ε are real constants that satisfy each of m>blk>0 and 2m>r>0, and ε>0,
(Concealing) Upper limit of information amount of B which Bob knows prior to the open phase is equal to or less than blk bits.
(Binding) At the open phase, it is assumed that there are r kinds of bit strings of B1, . . . , Br which Alice (who is dishonest) wants to open. Further, it is also assumed that probability of Bob's acceptance of each commitment is P1, . . . , Pr. At this time, P1+ . . . +Pr<1+ε is satisfied.
The above concealing requirements show that the information amount which Bob obtains from an evidence |ΨB is equal to or less than blk bits.
The above binding requirements show there is small possibility that Alice can change the value of the bit string B after the commit phase. For example, this is an image such that when Alice thinks it is sufficient to open any of 100 values of B afterwards, its success probability is around 1/100.
When each bit bi of the bit string B=(b1, . . . , bm) is committed through BC, none of bits of information of the B is leaked to Bob prior to the open phase. On the other hand, in case of QBSC, desired security is different, since the leakage up to blk bits is allowed.    Non-patent Document 1: A. Kent, “Quantum Bit String Commitment,” Phys. Rev. Lett., vol. 90, 237901, 2003    Non-patent Document 2: Tatsuaki Okamoto and Hiroshi Yamamoto, “Gendai Angou (Modern Cryptography),” Sangyo Tosho, 1997    Non-patent Document 3: “Supplementary volume: Suuri-Kagaku (April, 2003), Ryoshi-Joho-Kagaku to sono Tenkai (Quantum Information Science and its Development),” Science-sha, 2003    Non-patent Document 4: C. Bennett and G. Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pp. 175-179, 1984    Non-patent Document 5: H. -K. Lo and H. F. Chau, “Is Quantum Bit Commitment Really Possible?,” Phys. Rev. Lett., vol. 78,pp. 3410-3413, 1997    Non-patent Document 6: M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information”, Cambridge Univ. Press, 2000    Non-patent Document 7: C. H. Bennett et al., “Experimental Quantum Cryptography,” Proceedings of Eurocrypt '90,pp. 253-265, Springer Verlag, 1990    Non-patent Document 8: D. Bouwmeester et al., “The Physics of Quantum Information: Quantum Cryptography, Quantum Teleportation, Quantum Computation,” Springer Verlag, 2000    Non-patent Document 9: C. H. Bennett, “Quantum Cryptography Using Any Two Nonorthogonal States,” Phys. Rev. Lett., vol. 68, 3121, 1992